package leetcode.Hot100;

import leetcode.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Cheng Jun
 * Description: 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * k == lists.length
 * 0 <= k <= 10^4
 * 0 <= lists[i].length <= 500
 * -10^4 <= lists[i][j] <= 10^4
 * lists[i] 按 升序 排列
 * lists[i].length 的总和不超过 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @version 1.0
 * @date 2021/12/18 22:30
 */
public class mergeKLists {

    /**
     * 思路：k = 1，不用合并，k = 2，很好合并，k = 3, 先合并掉前面两，就又变成 k =2 的情况
     * 所以 我们设计一个合并 两个 链表的方法就行，这个 方法就是 mergeTwoLists
     * 考虑到 每次合并后链表越来越长，再下一次合并的时候会更花费时间，这里可以使用分治算法优化一下。
     * @see mergeTwoLists
     * @author Cheng Jun
     * @date 2021/12/18 22:31
     * @param lists
     * @return leetcode.ListNode
     */
    static ListNode mergeKLists(ListNode[] lists) {
        // 题目条件：-10^4 <= lists[i][j] <= 10^4
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        for (int i = 0; i < lists.length; i++) {
            dummy = mergeTwoLists.mergeTwoLists(dummy, lists[i]);
        }
        return dummy.next;
    }

    // 技巧：使用优先队列
    // 如果我们的链表都只有一个节点，我们把所有的链表放到 优先队列中，然后再出列就行了。
    // 在一个链表出列后，其实它可能还有next，这个next需要再次入列。
    static ListNode mergeKLists1(ListNode[] lists) {
        // 使用 小根堆，必须指定 比较器 Comparator，虽然 PriorityQueue 默认使用小根堆，但是 ListNode中没有比较器
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(l -> l.val));
        for (ListNode node : lists) {
            // 节点非空，才有比较的意义
            if (node != null) queue.add(node);
        }
        // 设置哑巴节点
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode tail = dummy;
        while (!queue.isEmpty()) {
            // 弹出最小值的节点
            ListNode minNode = queue.poll();
            tail.next = minNode;
            tail = tail.next;
            // 将 minNode 下一个节点 入列
            if (minNode.next != null) queue.add(minNode.next);
        }
        return dummy.next;
    }

}
